/*
*
给你一个 rows x cols 的矩阵 grid 来表示一块樱桃地。 grid 中每个格子的数字表示你能获得的樱桃数目。

你有两个机器人帮你收集樱桃，机器人 1 从左上角格子 (0,0) 出发，机器人 2 从右上角格子 (0, cols-1) 出发。

请你按照如下规则，返回两个机器人能收集的最多樱桃数目：

从格子 (i,j) 出发，机器人可以移动到格子 (i+1, j-1)，(i+1, j) 或者 (i+1, j+1) 。
当一个机器人经过某个格子时，它会把该格子内所有的樱桃都摘走，然后这个位置会变成空格子，即没有樱桃的格子。
当两个机器人同时到达同一个格子时，它们中只有一个可以摘到樱桃。
两个机器人在任意时刻都不能移动到 grid 外面。
两个机器人最后都要到达 grid 最底下一行。

示例 1：

输入：grid = [[3,1,1],[2,5,1],[1,5,5],[2,1,1]]
输出：24
解释：机器人 1 和机器人 2 的路径在上图中分别用绿色和蓝色表示。
机器人 1 摘的樱桃数目为 (3 + 2 + 5 + 2) = 12 。
机器人 2 摘的樱桃数目为 (1 + 5 + 5 + 1) = 12 。
樱桃总数为： 12 + 12 = 24 。
示例 2：

输入：grid = [[1,0,0,0,0,0,1],[2,0,0,0,0,3,0],[2,0,9,0,0,0,0],[0,3,0,5,4,0,0],[1,0,2,3,0,0,6]]
输出：28
解释：机器人 1 和机器人 2 的路径在上图中分别用绿色和蓝色表示。
机器人 1 摘的樱桃数目为 (1 + 9 + 5 + 2) = 17 。
机器人 2 摘的樱桃数目为 (1 + 3 + 4 + 3) = 11 。
樱桃总数为： 17 + 11 = 28 。
示例 3：

输入：grid = [[1,0,0,3],[0,0,0,3],[0,0,3,3],[9,0,3,3]]
输出：22
示例 4：

输入：grid = [[1,1],[1,1]]
输出：4

提示：

rows == grid.length
cols == grid[i].length
2 <= rows, cols <= 70
0 <= grid[i][j] <= 100

  - @author ala
  - @date 2024-09-27 14:46
*/
package main

import (
	"fmt"
	"math"
)

func main() {
	//grid := [][]int{{3, 1, 1}, {2, 5, 1}, {1, 5, 5}, {2, 1, 1}}
	//grid := [][]int{{1, 0, 0, 0, 0, 0, 1}, {2, 0, 0, 0, 0, 3, 0}, {2, 0, 9, 0, 0, 0, 0}, {0, 3, 0, 5, 4, 0, 0}, {1, 0, 2, 3, 0, 0, 6}}
	//grid := [][]int{{1, 0, 0, 3}, {0, 0, 0, 3}, {0, 0, 3, 3}, {9, 0, 3, 3}
	//grid := [][]int{{9, 0, 1, 4, 4, 5}, {0, 6, 1, 10, 2, 4}, {6, 8, 7, 1, 9, 3}, {2, 10, 9, 7, 6, 9}, {9, 4, 9, 2, 3, 0}, {3, 6, 2, 3, 8, 4}, {4, 10, 5, 0, 6, 7}, {8, 1, 7, 3, 7, 0}}
	grid := [][]int{{0, 8, 7, 10, 9, 10, 0, 9, 6}, {8, 7, 10, 8, 7, 4, 9, 6, 10}, {8, 1, 1, 5, 1, 5, 5, 1, 2}, {9, 4, 10, 8, 8, 1, 9, 5, 0}, {4, 3, 6, 10, 9, 2, 4, 8, 10}, {7, 3, 2, 8, 3, 3, 5, 9, 8}, {1, 2, 6, 5, 6, 2, 0, 10, 0}}

	fmt.Println(cherryPickup(grid))
}

func cherryPickup(grid [][]int) int {
	return V1(grid)
}

var (
	INF int = math.MinInt32 >> 1
)

/**
 *	1）dp[i][j1][j2]表示：第i行，处在j1,j2两个点，能摘到的最大樱桃数
 *	2）dp[i][j1][j2] = i - 1 层中，j1 与 j2 分别取 -1, 0, 1 时的最大值 + grid[i][j1] + grid[i][j2]
 *		如果 j1 == j2：grid[i][j2] = 0
 */
func V1(grid [][]int) int {
	M, N := len(grid), len(grid[0])

	dp := make([][][]int, M)
	for i := range dp {
		dp[i] = make([][]int, N)
		for j1 := range dp[i] {
			dp[i][j1] = make([]int, N)
		}
	}
	for j1 := range dp[0] {
		for j2 := range dp[0][j1] {
			dp[0][j1][j2] = INF
		}
	}
	dp[0][0][N-1] = grid[0][0] + grid[0][N-1]
	res := 0
	for i := 1; i < M; i++ {
		for j1 := range dp[i] {
			for j2 := range dp[i][j1] {
				v1 := INF
				if j2 > 0 {
					v11 := dp[i-1][j1][j2-1]
					v12 := INF
					if j1 > 0 {
						v12 = dp[i-1][j1-1][j2-1]
					}
					v13 := INF
					if j1 < N-1 {
						v13 = dp[i-1][j1+1][j2-1]
					}
					v1 = max(v11, v12, v13)
				}

				v21 := dp[i-1][j1][j2]
				v22 := INF
				if j1 > 0 {
					v22 = dp[i-1][j1-1][j2]
				}
				v23 := INF
				if j1 < N-1 {
					v23 = dp[i-1][j1+1][j2]
				}
				v2 := max(v21, v22, v23)

				v3 := INF
				if j2 < N-1 {
					v31 := dp[i-1][j1][j2+1]
					v32 := INF
					if j1 > 0 {
						v32 = dp[i-1][j1-1][j2+1]
					}
					v33 := INF
					if j1 < N-1 {
						v33 = dp[i-1][j1+1][j2+1]
					}
					v3 = max(v31, v32, v33)
				}
				g1, g2 := grid[i][j1], grid[i][j2]
				if j1 == j2 {
					g2 = 0
				}
				dp[i][j1][j2] = max(v1, v2, v3) + g1 + g2
				if i == M-1 {
					res = max(res, dp[i][j1][j2])
				}
			}
		}
	}
	return res
}
